package main

// Definition for a QuadTree node.
type Node struct {
	Val         bool
	IsLeaf      bool
	TopLeft     *Node
	TopRight    *Node
	BottomLeft  *Node
	BottomRight *Node
}

func construct(grid [][]int) *Node {
	N := len(grid)
	return _construct(grid, 0, N-1, 0, N-1)
}

func _construct(grid [][]int, r1, r2, c1, c2 int) *Node {
	if r1 > r2 || c1 > c2 {
		return nil
	}
	root := new(Node)
	if isSame(grid, r1, r2, c1, c2) {
		//叶子节点
		root.Val = grid[r1][c1] == 1
		root.IsLeaf = true
		return root
	} else {
		//非叶子节点
		root.Val = true //随意给个值
		root.IsLeaf = false
	}
	midR := (r1 + r2) / 2
	midC := (c1 + c2) / 2
	root.TopLeft = _construct(grid, r1, midR, c1, midC)
	root.TopRight = _construct(grid, r1, midR, midC+1, c2)
	root.BottomLeft = _construct(grid, midR+1, r2, c1, midC)
	root.BottomRight = _construct(grid, midR+1, r2, midC+1, c2)
	return root
}

func isSame(grid [][]int, r1, r2, c1, c2 int) bool {
	for i := r1; i <= r2; i++ {
		for j := c1; j < c2; j++ {
			if grid[i][j] != grid[r1][c1] {
				return false
			}
		}
	}
	return true
}

func main() {

}
